package secondary

/*
	给定一个由整数数组 A表示的环形数组 C，求 C的非空子数组的最大可能和。

	在此处，环形数组意味着数组的末端将会与开头相连呈环状。（形式上，当0 <= i < A.length时C[i] = A[i]，且当i >= 0时C[i+A.length] = C[i]）

	此外，子数组最多只能包含固定缓冲区 A中的每个元素一次。
	（形式上，对于子数组C[i], C[i+1], ..., C[j]，不存在i <= k1, k2 <= j其中k1 % A.length= k2 % A.length）

	示例 1：
	输入：[1,-2,3,-2]
	输出：3
	解释：从子数组 [3] 得到最大和 3

	示例 2：
	输入：[5,-3,5]
	输出：10
	解释：从子数组 [5,5] 得到最大和 5 + 5 = 10

	示例 3：
	输入：[3,-1,2,-1]
	输出：4
	解释：从子数组 [2,-1,3] 得到最大和 2 + (-1) + 3 = 4

	示例 4：
	输入：[3,-2,2,-3]
	输出：3
	解释：从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3

	示例 5：
	输入：[-2,-3,-1]
	输出：-1
	解释：从子数组 [-1] 得到最大和 -1

	提示：

	-30000 <= A[i] <= 30000
	1 <= A.length <= 30000

	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/maximum-sum-circular-subarray
	著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
/*
	// 假设最大子序列和在中间、直接按非环形数组的方式求解最大和normalSum
	// 假设最大子序列和在首尾相连处、则先算出整个数组的和sum、然后找到一个最小的连续子数组的序列和minSum
	// serialSum = sum-minSum是另一个有可能的最大和
	// 比较normalSum和 serialSum、返回其中较大值
*/
func MaxSubarraySumCircular(nums []int) int {
	return maxSubarraySumCircular(nums)
}

// 1, -2, 3, -2
func maxSubarraySumCircular(nums []int) int {
	size := len(nums)
	dpMax := make([]int, size)
	dpMin := make([]int, size)
	dpMax[0] = nums[0]
	sum := nums[0]
	maxSum := nums[0]
	minSum := nums[0]
	for i := 1; i < size; i++ {
		sum += nums[i]
		if nums[i]+dpMax[i-1] > nums[i] {
			dpMax[i] = dpMax[i-1] + nums[i]
		} else {
			dpMax[i] = nums[i]
		}
		if nums[i]+dpMin[i-1] < nums[i] {
			dpMin[i] = dpMin[i-1] + nums[i]
		} else {
			dpMin[i] = nums[i]
		}
		maxSum = max(maxSum, dpMax[i])
		minSum = min(minSum, dpMin[i])
	}
	if sum-minSum == 0 {
		return maxSum
	}
	return max(maxSum, sum-minSum)
}
